Light Detection and Ranging (LiDAR) is an emerging three-dimensional data acquisition technology, and may rapidly acquire massive point cloud data by using laser scanners carried on a tripod, a car, an aircraft, a satellite and other different platforms. The point cloud data contain latitude/longitude coordinates, intensity, multiple echoes, color and other rich information of each point, and are applied to surveying and mapping, forestry, agriculture, digital city and other fields. At present, common laser scanner equipment, such as Riegl, Faro and Leica, may produce thousands of points per second; number of data points acquired in each scan may reach hundreds of thousands or millions; a volume of data is up to dozens of to hundreds of G. Such a huge volume of data brings a burden to storing and processing of data.
How to effectively organize and manage, dynamically schedule and display massive data is essential to further analysis and application of data; and research in relevant fields is in full swing. Spatial index is a key technology in point cloud data organization and management; different spatial indexing modes have different structural complexities, constructions, query efficiencies and space utilization ratios. At present, common point cloud data spatial indexing modes include grid index, quadtree index, octree index and k-dimensional (KD) tree index. The grid index is easy to construct and code, but no spatial distribution situation of data is considered during construction, and is not conducive to rapid visualization of the point cloud data; the quadtree index is simple in structure, but it is difficult to determine number of points contained in leaf nodes when the quadtree index is constructed for massive point cloud, and construction and query efficiencies are reduced when distribution of data is uneven; the KD tree index is advantageous in query and retrieval of data, but a lot of time is needed to establish a neighborhood relation of points; the octree index is a three-dimensional spatial index structure expanded from the quadtree index to a three-dimensional space, is relatively simple in construction process, and has a high index efficiency; but for massive point cloud data, a larger memory space may be occupied when the index is constructed and query efficiency is also reduced with an increase of depth of an octree.